package com.kevin.Code.BinarySearch;

/**
 * @author Vinlee Xiao
 * @Classname Searcha2dMatrixii
 * @Description Leetcode 240. 搜索二维矩阵 II 中等难度  二分查找二刷
 * @Date 2022/2/27 10:16
 * @Version 1.0
 */
public class Searcha2dMatrixii {

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;

        if (row == 1 && col == 1) {
            return target == matrix[0][0];
        }
        for (int[] arr : matrix) {

            if (col > 1 && arr[0] <= target && arr[col - 1] >= target) {
                int res = binarySearch(arr, 0, col - 1, target);
                if (res != -1) {
                    return true;
                }
            } else if (col == 1 && arr[0] == target) {
                return true;
            }

        }

        return false;

    }

    /**
     *
     */
    public int binarySearch(int[] nums, int low, int high, int target) {

        while (low <= high) {
            int mid = (low + high) >> 1;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }

        }

        return -1;
    }

    public static void main(String[] args) {
        int[][] nums = new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30, 5}};
        Searcha2dMatrixii searcha2dMatrixii = new Searcha2dMatrixii();
        boolean b = searcha2dMatrixii.searchMatrix(nums, 5);
        System.out.println(b);
    }
}
